// 10.2 初识泛型算法
/**
 * 标准库提供了超过100个算法。幸运的是，与容器类似，这些算法有一致的结构。
 * 比起死记硬背全部100多个算法，理解此结构可以帮助我们更容易地学习和使用这些算法。
 * 除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。
 * 接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器。
 */

#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <string>
#include <array>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
using std::swap;
using std::vector, std::list, std::deque, std::forward_list, std::string, std::array, std::stack, std::queue;
#include "../Chapter07/Sales_data.h"
#include <iostream>
using std::begin, std::cbegin, std::end, std::cend, std::find, std::accumulate, std::equal, std::fill, std::fill_n, std::back_inserter;
using std::cin, std::cout, std::endl;
using std::copy, std::replace, std::replace_copy;

int main()
{
    // 10.2.2 写容器元素的算法
    // 记住，算法不会执行容器操作，因此它们自身不可能改变容器的大小。
    vector<int> vec{1, 2, 3, 4, 5, 6, 7};
    fill(vec.begin(), vec.end(), 0);                     // 将每个元素重置为0
    fill(vec.begin(), vec.begin() + vec.size() / 2, 10); // 将容器的一个子序列设置为10

    // 关键概念：迭代器参数
    // 对equal算法，元素类型不要求相同，但是我们必须能使用==来比较来自两个序列中的元素。
    // 一些算法，例如equal，接受三个迭代器：前两个表示第一个序列的范围，第三个表示第二个序列中的首元素。

    // 算法不检查写操作
    // 例如：函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。
    vector<int> vec1;                     // 空vector
    fill_n(vec1.begin(), vec1.size(), 0); // 将所有元素重置为0
    // fill_n(vec1.begin(), 10, 0);          // 灾难：修改vec中的10个（不存在）元素

    // 介绍back_inserter
    // 一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器（insertiterator）。插入迭代器是一种向容器中添加元素的迭代器。
    // back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。
    // 当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中：[插图]
    vector<int> vec2;              // 空向量
    auto it = back_inserter(vec2); // 返回插入迭代器，通过它赋值会将元素添加到vec2中
    *it = 42;                      // vec2中现在有个元素，值为42
    // 我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。例如：[插图]
    vector<int> vec3;                   // 空向量
    fill_n(back_inserter(vec3), 10, 0); // 添加10个0到vec3中

    // 拷贝算法
    // 拷贝（copy）算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。
    // 此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。
    int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int a2[sizeof(a1) / sizeof(*a1)]; // a2与a1大小一样
    // sizeof(a1)/sizeof(a1[0]) 可以获取数组的长度，原理是 sizeof(a1) 代表整个数组的大小，sizeof(a1[0]) 代表数组中第一个元素的大小
    // 而数组中的每个元素大小都是相同的，所以最后的计算结果就是数组的长度。
    cout << sizeof(a1) << endl;              // 40
    cout << sizeof(*a1) << endl;             // 4
    auto ret = copy(begin(a1), end(a1), a2); // 把a1的内容拷贝给a2
    replace(begin(a1), end(a1), 0, 42);      // 将所有值为0的元素改为42
    // 如果我们希望保留原序列不变，可以调用replace_copy。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：
    vector<int> ivec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    replace_copy(cbegin(a2), cend(a2), back_inserter(ivec), 0, 42);

    return 0;
}